package algorithm.linkedList;

/**
 * 将两个有序链表合并为一个大的有序链表
 * 需要把握的是pre,cur1,cur2三个指针指向哪里
 * 1. pre初始化为新链表的头部
 * 2. cur1指向新链表头部的next
 * 3. cur2指向另一个链表的头部
 * 链表的变化如下：
 * 1. 如果下一个节点是1号链表：将cur1挂到pre的next，cur1向前遍历
 * 2. 如果下一个链表是2号链表，将cur2挂到pre的next，cur2向前遍历
 * 3. 每一趟循环都需要向前移动pre
 */
public class ListMerge {
    public static ListNode listMerge(ListNode head1,ListNode head2){
        if(head1==null||head2==null){
            return head1==null?head2:head1;
        }
        ListNode head=head1.val<=head2.val?head1:head2;
        ListNode cur1=head.next;
        ListNode cur2=head==head1?head2:head1;
        ListNode pre=head;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                pre.next=cur1;
                cur1=cur1.next;
            }else{
                pre.next=cur2;
                cur2=cur2.next;
            }
            pre=pre.next;
        }
        pre.next=cur1!=null?cur1:cur2;
        return head;
    }
}
